//049. 素数排列
//        1487, 4817, 8147 这个序列，每个比前一个递增 3330，而且这个序列有两个特点：
//        1. 序列中的每个数都是质数。
//        2. 每个四位数都是其他数字的一种排列。
//        没有一位、两位和三位素数组成的序列满足上面的性质，但是还有一组满足这个性质的四位
//        数递增序列。这个序列的三个数前后拼接组成的十二位数是多少？
//        答案：296962999629

public class Week049 {
    static boolean isPrime(int x) {
        return Week041.isPrime(x);
    }

    //判断x是否是y的一种排列
    static boolean check(int x, int y) {
        int[] count = new int[10];
        while (x != 0) {
            ++count[x % 10];
            x /= 10;
        }
        while (y != 0) {
            --count[y % 10];
            if (count[y % 10] < 0) return false;
            y /= 10;
        }
        return true;
    }

    static void run() {
        final int Difference = 3330;
        //偶数一定不是质数，间隔为1的遍历
        //要递增两次3330，且为四位数，所以最终只能遍历至3339
        for (int i = 1001; i <= 3339; i += 2) {
            if (!isPrime(i)) continue;
            int a = i + Difference, b = a + Difference;
            if (isPrime(a) && check(i, a) && isPrime(b) && check(i, b)) {
                System.out.print(i);
                System.out.print(a);
                System.out.print(b);
                System.out.println();
            }

        }
    }

    public static void main(String[] args) {
        long startTime = System.nanoTime();
        run();
        System.out.println("\n程序运行时间：" + (System.nanoTime() - startTime) + "ns.");
    }
}
